#include<stdio.h>
#include<stdlib.h>
typedef enum { false, true } bool;

#define MaxVertexNum 1000
typedef int Vertex;
typedef int WeightType;

typedef struct ENode* PtrToENode;
struct ENode {
	Vertex V1, V2;
};
typedef PtrToENode Edge;

typedef struct GNode* PtrToGNode;
struct GNode {
	int Nv;
	int Ne;
	WeightType G[MaxVertexNum][MaxVertexNum];
	int Degree[MaxVertexNum];
};
typedef PtrToGNode MGraph;
bool Visited[MaxVertexNum];

MGraph CreateGraph(int VertexNum);
void InsertEdge(MGraph Graph, Edge E);
MGraph BuildGraph();
void DFS(MGraph Graph, Vertex V);
bool CheckG(MGraph Graph);

int main()
{
	Vertex V;
	MGraph Graph = BuildGraph();
	DFS(Graph, 0);
	for (V = 0; V < Graph->Nv; V++)
		if (!Visited[V]) break;
	if (V < Graph->Nv)
		printf("0\n");
	else
		printf("%d\n", CheckG(Graph));
	return 0;
}

MGraph CreateGraph(int VertexNum)
{
	Vertex V, W;
	MGraph Graph;
	Graph = (MGraph)malloc(sizeof(struct GNode));
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
	for (V = 0; V < Graph->Nv; V++) {
		Graph->Degree[V] = 0;
		for (W = 0; W < Graph->Nv; W++)
			Graph->G[V][W] = 0;
	}
	return Graph;
}

void InsertEdge(MGraph Graph, Edge E)
{
	Graph->G[E->V1][E->V2] = 1;
	Graph->Degree[E->V1]++;
	Graph->G[E->V2][E->V1] = 1;
	Graph->Degree[E->V2]++;
}

MGraph BuildGraph()
{
	MGraph Graph;
	Edge E;
	Vertex V;
	int Nv, i;
	scanf("%d", &Nv);
	Graph = CreateGraph(Nv);
	scanf("%d", &(Graph->Ne));
	if (Graph->Ne != 0) {
		E = (Edge)malloc(sizeof(struct ENode));
		for (i = 0; i < Graph->Ne; i++) {
			scanf("%d %d", &E->V1, &E->V2);
			E->V1--; E->V2--;
			InsertEdge(Graph, E);
		}
	}
	return Graph;
}

void DFS(MGraph Graph, Vertex V)
{
	Vertex W;
	Visited[V] = true;
	for (W = 0; W < Graph->Nv; W++)
		if (!Visited[W] && (Graph->G[V][W]))
			DFS(Graph, W);
}

bool CheckG(MGraph Graph)
{
	Vertex V;
	for (V = 0; V < Graph->Nv; V++)
		if (Graph->Degree[V] % 2) return false;
	return true;
}
